package top.truism.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 带有 getMin 操作的栈
 */
public class GetMinStack<T extends Comparable<T>> {

    private Deque<T> stack;

    private Deque<T> minStack;

    public GetMinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(T t) {
        stack.push(t);
        if(minStack.size() == 0 || t.compareTo(minStack.peek()) < 0) {
            minStack.push(t);
        }else {
            minStack.push(minStack.peek());
        }
    }

    public T pop() {
        minStack.pop();
        return stack.pop();
    }

    public T getMin() {
        return minStack.peek();
    }

}
